package 每日一题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No740删除并获得点数 {

    /**
     * 给你一个整数数组 nums ，你可以对它进行一些操作。
     * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。
     * 之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。
     * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
     *
     * 示例 1：
     * 输入：nums = [3,4,2]
     * 输出：6
     * 解释：
     * 删除 4 获得 4 个点数，因此 3 也被删除。
     * 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
     * 示例 2：
     * 输入：nums = [2,2,3,3,3,4]
     * 输出：9
     * 解释：
     * 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
     * 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
     * 总共获得 9 个点数。
     *  
     * 提示：
     * 1 <= nums.length <= 2 * 104
     * 1 <= nums[i] <= 104
     */

    private class Pair{
        public int num;
        public int sum;
        public Pair(int num, int sum) {
            this.num = num;
            this.sum = sum;
        }
    }

    //最优解法:将相同的数值汇总,然后就转为打家劫舍的问题了
    public int deleteAndEarn(int[] nums) {

        /**
         * 还可以继续极致一点,空间换时间,题目说nums[i].max=104,那可以直接创建104大小数组,
         * 然后遍历数组,将对应的值加到对应的下标,然后最后开始遍历 这 104大小 数组,直接隔代dp。
         */
        Arrays.sort(nums);

        List<Pair> list=new ArrayList<>();
        int sum=nums[0];

        for (int i = 1; i < nums.length; i++) {
            if(nums[i]==nums[i-1]){
                sum+=nums[i];
            }else{
                list.add(new Pair(nums[i-1],sum));
                sum=nums[i];
            }
        }
        //出列更新最后一个元素
        list.add(new Pair(nums[nums.length-1],sum));

        //然后开始dp
        int[] dp=new int[list.size()];

        //base
        dp[0]=list.get(0).sum;

        for (int i = 1; i < list.size(); i++) {

            if(list.get(i-1).num+1==list.get(i).num){
                //相邻,不是很好
                dp[i]=Math.max(dp[i-1],list.get(i).sum+(i-2<0?0:dp[i-2]));
            }else{
                //不相邻,挺好
                dp[i]=Math.max(dp[i-1],dp[Math.max(i-2,0)])+list.get(i).sum;
            }

        }

        return dp[dp.length-1];

    }

    //不是最优解法
    public int deleteAndEarnNormal(int[] nums) {

        Arrays.sort(nums);

        //{要自己,不要自己}
        int[][] dp=new int[nums.length][2];

        //base
        int baseNum=nums[0];
        dp[0][0]=nums[0];
        int i = 1;
        for (; i < nums.length; i++) {
            if(baseNum==nums[i]){
                dp[i][0]=dp[i-1][0]+nums[i];
                dp[i][1]=0;//默认
            }else{
                break;
            }
        }

        //然后开始
        for(; i<nums.length; i++){

            if(nums[i-1]+1==nums[i]){
                //紧挨着,生效
                //需要知道上一位的起始
                int index=-1;
                for (int j = i-1; j >=0 ; j--) {
                    if(nums[j]!=nums[i-1]){
                        index=j;
                        break;
                    }
                }
                dp[i][0]=index==-1?nums[i]:nums[i]+Math.max(dp[index][0],dp[index][1]);
                dp[i][1]=dp[i-1][0];
            }else if(nums[i-1]==nums[i]){
                //相等的
                dp[i][0]=dp[i-1][0]+nums[i];
                dp[i][1]=dp[i-1][1];
            }else{
                //跨越性的,可以直接
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1])+nums[i];
                dp[i][1]=Math.max(dp[i-1][0],dp[i-1][1])+nums[i];
            }

        }

        return Math.max(dp[dp.length-1][0],dp[dp.length-1][1]);
    }

    public static void main(String[] args) {
        No740删除并获得点数 n=new No740删除并获得点数();
        int[] arr={2,2,3,3,3,4};
        int result = n.deleteAndEarn(arr);
        System.out.println(result);
    }

}
